package br.unicamp.ic.mc906.kmeans;

import java.util.ArrayList;
import java.util.List;

/**
 * Classe responsavel pela clusteriza��o K-means
 */
public class Kmeans<T extends KmeansInterface<T>> {
	
	private List<Cluster<T>> clusters = new ArrayList<Cluster<T>>();

	/**
	 * Metodo que faz a clusterizacao dos elementos do vetor 
	 * @param elements
	 * @return
	 */
	public List<List<T>> cluster(List<T> elements, int k) {
		
		// Verifica se K � maior ou igual a n
		if (k >= elements.size()) {
			System.out.println("K shouldnt be greater then N");
			return null;
		}
		
		// Verifica se a lista de elementos � valida
		if (elements == null || elements.size() == 0) {
			System.out.println("The elements list has no objects");
		}
		
		// Inicializa lista de indices adicionados para impedir que elementos
		// sejam adicionados como cluster mais de uma vez.
		List<Integer> indices = new ArrayList<Integer>(); 
		
		// Inicializa os k Centroides
		for (int i=0; i< k; i++) {
			// Randomiza os elementos do vetor
			int x = ((Number)(Math.random()*elements.size())).intValue();
			
			
			// Garante que o mesmo index seja usado em outro centroide
			while(indices.contains(x)) {
				x = ((Number)(Math.random()*elements.size())).intValue();
			}
			indices.add(x);
			Centroide<T> centroid = new Centroide<T>(elements.get(x));
//			Centroide<T> centroid = new Centroide(elements.get(0).getRandomElement());
			Cluster<T> cluster = new Cluster<T>(centroid);
			clusters.add(cluster);
		}
		
		// Faz o para todo elemento restante faz o calculo das distancias
		int index = 0;
		for (T element : elements) {
			clusters.get(index%k).addElementToCluster(element);
//			double min = Double.MAX_VALUE;
//			Cluster<T> cluster = null;
//			for (Cluster<T> c : clusters) {
//				double current = c.getCentroid().distanceToCentroid(element);
//				if (current < min) {
//					min = current;
//					cluster = c;
//				}
//			}
//			cluster.addElementToCluster(element);
			index++;
		}

		boolean change = true;
		int i = 0;
		// Enquanto ainda existe mudanca de cluster executa
		while (change && i < k*elements.size()) {
			change = false;
			
			// Muda os elementos de cluster visando minimizar a soma dos quadrados
			for (T element : elements) {
				Cluster<T> current = belongsTo(element);
				Cluster<T> newest = current;

				// Para todos os cluster verifica se a distancia entre os centroides sao menores.
				for (Cluster<T> cluster : clusters) {
					if (cluster != current) {
						double newDistance = newest.getCentroid().distanceToCentroid(element);
						double clusterDistance = cluster.getCentroid().distanceToCentroid(element);
						if (clusterDistance < newDistance) {
							newest = cluster;
							change = true;
						}
					}
				}
				
				// Faz a troca de cluster se necessario
				if (change == true && current != newest) {
					current.removeElementFromCluster(element);
					newest.addElementToCluster(element);
				}
				
			}
			i++;
			
			// Recalcula as centroides dos clusters
			for (Cluster<T> cluster : clusters) {
				Centroide<T> centroid = new Centroide<T>(elements.get(0).centroidOfCluster(cluster.getData()));
				cluster.setCentroid(centroid);
			}
			
		}
		
		// Monta a resposta
		List<List<T>> response = new ArrayList<List<T>>();
		for (Cluster<T> c : clusters) {
			System.out.println(c);
			List<T> data = new ArrayList<T>();
			for (T element : c.getData()) {
				data.add(element);
			}
			response.add(data);
		}
		
		return response;
	}
	
	
	/**
	 * Metodo que retorna o cluster a qual um elemento pertence
	 * @param element
	 * @return
	 */
	private Cluster<T> belongsTo(T element) {
		for (Cluster<T> c : clusters) {
			if (c.contains(element)) {
				return c;
			}
		}
		return null;
	}
	
}
